package ListNodeSecond.SwordOffer;

import java.util.Stack;

public class ReorderList {
    /**
     * 剑指 Offer II 026. 重排链表
     * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
     * <p>
     * L0 → L1 → … → Ln-1 → Ln
     * 请将其重新排列后变为：
     * <p>
     * L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
     * <p>
     * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     *
     * 没搞太懂这个玩意
     */
    public static void reorderList(ListNode head) {
        // 使用双指针找到中点的位置，并进行标记
        if (head.next == null)
            return;
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = slow;

        // 开始入栈
        Stack<ListNode> stack = new Stack<>();
        while (slow != null) {
            // 使用临时节点记录位置，并将连接断开依次入栈
            ListNode temp = slow;
            slow = slow.next;
            temp.next = null;
            stack.push(temp);
        }

        // 返回开始点，依次连接正序链表和出栈的节点
        // 直到到标记的中点结束
        slow = head;
        while (slow != fast) {
            ListNode temp = slow.next;
            slow.next = stack.pop();
            slow = slow.next;
            if (slow != temp) {
                slow.next = temp;
                slow = slow.next;
            }
        }
        System.out.println(head.toString());
    }
//    public static void reorderList(ListNode head) {
//        if(head == null || head.next == null)
//            return;
//        ListNode midNode = getMid(head); //  midNode 3->4->5  head 1->2
//        ListNode head1 = reverseList(midNode); //head1 5->4->3
//        ListNode merge = merge(head, head1);
//        System.out.println(merge.toString());
//    }


    // 获取中间结点
    public static ListNode getMid(ListNode head) {
        if (head == null) return head;
        ListNode slow = head;
        ListNode fast = head;
        //定义一个temp节点，就可以将head了，如果不定义就不行
        ListNode temp = null;
        while (fast != null && fast.next != null) {
            temp = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        temp.next = null;
        return slow;
    }


    //翻转链表
    public static ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;  //2->3         // 3           //null
            cur.next = pre;            //1->null      //2->1->null   //3->2->1->null
            pre = cur;                 //1->null      //2->1->null   //3->2->1->null
            cur = temp;                //cur = 2->3   //cur = 3      // cur = null;
        }
        return pre;
    }

    // 合并链表 1 5 2 4 3         (1 2)           (5 4 3)
    public static ListNode merge(ListNode head, ListNode head1) {
        ListNode p = head;
        ListNode cur = head1;
        while (cur != null) {
            ListNode next = cur.next;  // next 4->3        3
            cur.next = p.next;         //      5->2        4->null
            p.next = cur;              //      1->5->2     1->5->2->4
            cur = next;                //  cur 4->3        3
            // 总数是奇数或者偶数，最后一个结点插入方法不同。
            if (p.next.next != null)
                p = p.next.next;
            else
                p = p.next;
        }
        return head;
    }


    public static void main(String[] args) {
        ListNode head = new ListNode(1);

        ListNode head1 = new ListNode(2);
        ListNode head2 = new ListNode(3);

        ListNode head3 = new ListNode(4);
        ListNode head4 = new ListNode(5);
        head.next = head1;
        head1.next = head2;
        head2.next = head3;
        head3.next = head4;
//      1 2 3 4 5    1 5 2 4 3
//        ListNode listNode =
//        System.out.println(listNode.toString());
        ListNode mid = getMid(head);
////        System.out.println(mid.toString());
//        ListNode listNode = reverseList(mid);
        reorderList(head);
    }
}
